package com.leetcode.题库;

/**
 * @author 覃国强
 * @date 2022-03-24 16:59
 */
public class 题库_0430_扁平化多级双向链表 {

  public static void main(String[] args) {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);

    node1.child = node2;
    node2.child = node3;


    Solution solution = new Solution();
    Node flatten = solution.flatten(node1);

    System.out.println(flatten);

  }


  static
  class Solution {

    public Node flatten(Node head) {

      Node sentinelHead = new Node();
      sentinelHead.child = head;

      flattenChild(sentinelHead);

      return head;
    }

    private Node flattenChild(Node head) {
      Node childHead = head.child;
      Node answerTail = childHead;
      while (childHead != null) {
        answerTail = childHead;
        if (childHead.child != null) {
          Node next = childHead.next;
          Node childTail = flattenChild(childHead);
          childTail.next = next;
          if (next != null) {
            next.prev = childTail;
          }

          childHead.next = childHead.child;
          childHead.next.prev = childHead;

          childHead.child = null;

          childHead = next;
          answerTail = childTail;
        } else {
          childHead = childHead.next;
        }
      }

      return answerTail;
    }
  }

  static
  class Node {

    public int val;
    public Node prev;
    public Node next;
    public Node child;

    Node() {

    }

    Node(int val) {
      this.val = val;
    }

  }

}
